package main

//"strconv"

/**
 * 给定不同面额的硬币和一个总金额。
 * 写出函数来计算可以凑成总金额的硬币组合数。
 * 假设每一种面额的硬币有无限个。
 */
var coinCnt int = 0

func solve(coins []int, target int) int {
	// TODO
	coinCnt = 0
	backtracking(coins, target, 0, 0)
	return coinCnt
}

func backtracking(coins []int, target int, path int, startIndex int) {
	//退出条件
	if path > target {
		return
	}

	if path == target {
		coinCnt++
	}

	for i := startIndex; i < len(coins); i++ {	
		path += coins[i]
		backtracking(coins, target, path, i)
		path -= coins[i]
	}
}

func main() {
	println(solve([]int{1, 2, 5}, 3) == 2)
	println(solve([]int{1, 2, 5}, 7) == 6)
	println(solve([]int{1, 2, 5}, 9) == 8)
	println(solve([]int{1, 2, 5}, 10) == 10)
	println(solve([]int{1, 2, 5}, 20) == 29)
	println(solve([]int{7}, 0) == 1)
	println(solve([]int{2}, 3) == 0)
	println(solve([]int{1, 2}, 9) == 5)
}
